For anyone curious, 3-clip APS tetris is perfectly dense at 29x29
(Apologies for the colors graphical design is not my passion)
I've tried a few algorithms to generate optimal aps tetris packings - recursive search algorithms (DFS/BFS), genetic algorithm, simulated annealing, CP-SAT solving with Google's OR-tools, and then finally ended up using CNF/DIMACS solving with cryptominisat5, which turns out is stupidly fast for this sorta thing.
Most important thing for the implementation is having it work backwards from theoretical maximum density using a cells unfilled constraint on the formula - this guarantees an optimal solution.
I'll probably release it when I get the time to make a proper UI and also try my hand at forcing symmetry.
(Apologies for the colors graphical design is not my passion)
I've tried a few algorithms to generate optimal aps tetris packings - recursive search algorithms (DFS/BFS), genetic algorithm, simulated annealing, CP-SAT solving with Google's OR-tools, and then finally ended up using CNF/DIMACS solving with cryptominisat5, which turns out is stupidly fast for this sorta thing.
Most important thing for the implementation is having it work backwards from theoretical maximum density using a cells unfilled constraint on the formula - this guarantees an optimal solution.
I'll probably release it when I get the time to make a proper UI and also try my hand at forcing symmetry.